// Package _2_将单链表按照某个值划分成左边小右边大的形式 main
// @Title _2_将单链表按照某个值划分成左边小右边大的形式
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-01-14 13:16
// @Create  2022-01-14 13:16
package main

import "fmt"

type LinkList struct {
	Val  int
	Next *LinkList
}

func main() {
	head := LinkList{
		4,
		&LinkList{
			6,
			&LinkList{
				3,
				&LinkList{
					5,
					&LinkList{
						1,
						nil,
					},
				},
			},
		},
	}
	fmt.Println(display(&head))
	res := changeLinkList(&head, 3)
	fmt.Println(display(res))
}

func display(head *LinkList) []int {
	if head == nil {
		return nil
	}
	var ans []int
	for head != nil {
		ans = append(ans, head.Val)
		head = head.Next
	}
	return ans
}

//
//  changeLinkList
//  @Description: 把单链表每一个节点放到数组里去，完事了构建一个新的链表，返回  笔试做法
//  @param head：
//  @return *LinkList：
//
func changeLinkList(head *LinkList, target int) *LinkList {
	if head == nil {
		return nil
	}
	var ans []*LinkList
	for head != nil {
		ans = append(ans, head)
		head = head.Next
	}
	index := -1
	index2 := -1
	for i := 0; i < len(ans); i++ {
		if ans[i].Val < target {
			index++
			ans[i], ans[index] = ans[index], ans[i]
		} else if ans[i].Val == target {
			index2++
			ans[i], ans[index2] = ans[index2], ans[i]
		} else { // 找到比自己大的
			if ans[index2].Val <= target {
				index2 = i
			}
		}
		fmt.Println(index, index2)
	}
	temp := &LinkList{0, head}
	phead := temp
	for i := 0; i < len(ans); i++ {
		ans[i].Next = nil
		temp.Next = ans[i]
		temp = temp.Next
	}
	return phead.Next
}

//
//  changeLinkListO1
//  @Description: 使用有限几个变量实现  一共六个变量
//  @param head：
//  @return *LinkList：
//
func changeLinkListO1(head *LinkList) *LinkList {
	if head == nil {
		return nil
	}
	return nil
}
